package org.example.SolutionNew004;

import java.util.ArrayList;
import java.util.List;

public class GraphTheory002 {
    public static void main(String[] args) {
        GraphTheory002 gt = new GraphTheory002();
//        int[][] grid=new int[][]{{2,1,1},{1,1,0},{1,0,1}};
        int[][] grid=new int[][]{{0}};
        System.out.println(gt.orangesRotting(grid));
    }

    int time=0;
    int count=0;
    int[] horizontal=new int[]{1,-1,0,0};
    int[] vertical=new int[]{0,0,1,-1};


    public int orangesRotting(int[][] grid) {
        //要么就把腐烂的橘子全都放到列表中然后腐烂计算次数
        int m=grid.length,n=grid[0].length;
        if(grid==null||m==0||n==0) return 0;
        List<List<Integer>> list=new ArrayList<>();
        for(int i=0;i<m;i++){
            for(int j=0;j<n;j++){
                if(grid[i][j]==2){
                    List<Integer> temp=new ArrayList<>();
                    temp.add(i);temp.add(j);
                    list.add(temp);
                }else if(grid[i][j]==1){
                    count++;
                }
            }
        }
        if(count==0) return 0;
        if(!list.isEmpty()) rotting(grid,list);
        if(count!=0) return -1;
        return time-1;
    }

    public void rotting(int[][] grid, List<List<Integer>> list) {
        List<List<Integer>> temp=new ArrayList<>();
        int m=grid.length,n=grid[0].length;
        for(List<Integer> l:list){
            int r=l.get(0),c=l.get(1);
            for(int i=0;i<4;i++){
                if(r+horizontal[i]>=0&&r+horizontal[i]<m&&c+vertical[i]>=0&&c+vertical[i]<n&&grid[r+horizontal[i]][c+vertical[i]]==1){
                    grid[r+horizontal[i]][c+vertical[i]]=2;
                    List<Integer> temp2=new ArrayList<>();
                    temp2.add(r+horizontal[i]); temp2.add(c+vertical[i]);
                    temp.add(temp2);
                    count--;
                }
            }
        }
        time++;
        if(!temp.isEmpty()) rotting(grid,temp);
    }
}
